/**
 * https://leetcode.cn/problems/time-needed-to-inform-all-employees/submissions/582660590/
 * 1376.通知所有员工所需的时间 1561
 * medium 陈贝纯 2024.11.24
 * dfs
 */


class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<vector<int>> adj(n);
        for(int i=0;i<n;++i){
            if(i!=headID)
                adj[manager[i]].push_back(i);
        }
        vector<int> Time(n,0);
        queue<int> q;
        q.emplace(headID);
        while(!q.empty()){
            int a=q.front();
            q.pop();
            for(auto num:adj[a]){
                Time[num]=Time[a]+informTime[a];
                q.emplace(num);
            }
        }
        sort(Time.begin(),Time.end(),greater<int>());
        return Time[0];
    }
};